// 78. 子集
// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

// 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

// 示例 1：

// 输入：nums = [1,2,3]
// 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 var subsets = function(nums) {
    const res=[],ans=[];
    const backtracking=function(start){
        if(ans.length<=nums.length){
            res.push([...ans]);
        }
        for(let i=start;i<nums.length;i++){
            ans.push(nums[i]);
            backtracking(i+1);
            ans.pop();
        }
    }
    backtracking(0);
    return res;
};

// 90. 子集 II(去重)
// 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

// 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

 

// 示例 1：

// 输入：nums = [1,2,2]
// 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 var subsetsWithDup = function(nums) {
    let res=[],ans=[];
    nums.sort((a,b)=>a-b);
    const backtracking=function(start){
        if(ans.length<=nums.length){
            res.push([...ans]);
        }
        for(let i=start;i<nums.length;i++){
            
            if(i>start&&nums[i-1]==nums[i]){
                continue
            };
            ans.push(nums[i]);
            backtracking(i+1);
            ans.pop();
        }
    }
    backtracking(0);
    return res;
};